Polygons
Memory limit: 32 MB
Yesterday Little John had a test on geometry.
The description of the most difficult problem follows.
Given two triangles
and
,
calculate the area of region
, which is defined as follows:
.
For example, if
has the vertices
,
,
and
has the vertices
,
,
, then
is a polygon
with the vertices
,
,
and
, so its area is
.
Afterwards, John started to wonder how to solve a modified problem -
"How to calculate area of
, if
and
are arbitrary
convex polygons". Little John has a test on biology tomorrow and has no time to solve
this problem himself. He asked you for help in solving this task.
Task
Write a program, which:
- reads the descriptions of two convex polygons
and
,
- computes the area of
,
- writes it doubled to the standard output.
Input
The first line of the standard input contains two integers
and
(
) separated with a single space and denoting
the numbers of vertices of polygons
and
.
In the second line there are
pairs of integers
(
), denoting the coordinates of consecutive vertices of the polygon
(in the clockwise order). In the third line there are
pairs of integers
(
) denoting the coordinates of consecutive vertices of the polygon
(in the clockwise order).
Output
The first and only line should contain one integer -
doubled area of
.
Example
For the input data:
4 4
0 0 0 1 2 1 2 0
0 0 0 2 1 2 1 0
the correct result is:
18
Task author: Piotr Stanczyk.